package ndfs.tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

import graph.State;
import graph.Graph;
import ndfs.NDFS;
import ndfs.Result;
import ndfs.CycleFound;
import ndfs.NoCycleFound;

public class NNDFS implements NDFS {

	private int threadId = 0;
	private Graph graph;
	private Colors colors;
	private Map<State, Boolean> pink;
	private Tree tree;

	public NNDFS(Graph graph, Map<State,Color> map,
			Tree tree) {
		this.graph = graph;
		this.colors = new Colors(map);
		this.pink = new HashMap<State, Boolean>();
		this.tree = tree;

	}

	public void init() {
	}

	public void setThreadId(int thread) {
		threadId = thread;
	}

	private Queue<State> getSortedQueue(State s) {
		Queue<State> result = new LinkedList<State>();

		List<State> allStates = graph.post(s);
		for (int i = 0; i < allStates.size(); i++) {
			// TODO Slim maniertje om threads the verdelen.
			result.add(allStates.get((threadId + i) % allStates.size()));
		}

		return result;
	}

	private boolean isRed(State s) {
		return tree.isRed(s.hashCode());
	}

	private void dfsRed(State s) throws Result {
		pink.put(s, true);
		Queue<State> sortedQueue = getSortedQueue(s);
		int states = sortedQueue.size();
		for (int i = 0; i < states; i++) {
			State t = sortedQueue.remove();
			if (colors.hasColor(t, Color.CYAN)) {
				throw new CycleFound();
			}
			Boolean b = pink.get(t);
			if ((b == null || b == false) && !isRed(t)) {
				dfsRed(t);
			}

			// else if (colors.hasColor(t, Color.BLUE)) {
			// colors.color(t, Color.RED);
			// dfsRed(t);
			// }
		}

		if (s.isAccepting()) {
			decrementCounter(s);
			awaitCounterIsZero(s);
		}
		
		// Make s red
		tree.setRed(s.hashCode());
		
		pink.put(s, false);

	}

	private void awaitCounterIsZero(State s) {
		boolean running = true;
		while (running) {
			running = !checkZero(s);
		}
	}

	private boolean checkZero(State s) {
		return tree.getCounter(s.hashCode()) == 0;
	}

	private void decrementCounter(State s) {
		tree.decrementCounter(s.hashCode());
	}

	private void incrementCounter(State s) {
		tree.incrementCounter(s.hashCode());
	}

	private void dfsBlue(State s) throws Result {
		colors.color(s, Color.CYAN);
		Queue<State> sortedQueue = getSortedQueue(s);
		int states = sortedQueue.size();
		for (int i = 0; i < states; i++) {
			State t = sortedQueue.remove();
			if (colors.hasColor(t, Color.WHITE) && !isRed(t)) {
				dfsBlue(t);
			}
		}
		if (s.isAccepting()) {
			incrementCounter(s);
			dfsRed(s);
		}
		colors.color(s, Color.BLUE);

	}

	private void nndfs(State s) throws Result {
		dfsBlue(s);
		throw new NoCycleFound();
	}

	public void ndfs() throws Result {
		nndfs(graph.getInitialState());
	}
}


//package ndfs.mcndfs_2;
//
//import java.util.HashMap;
//import java.util.LinkedList;
//import java.util.List;
//import java.util.Map;
//import java.util.Queue;
//
//import graph.State;
//import graph.Graph;
//import ndfs.NDFS;
//import ndfs.Result;
//import ndfs.CycleFound;
//import ndfs.NoCycleFound;
//
//public class NNDFS implements NDFS {
//
//	private int threadId = 0;
//	private Graph graph;
//	private Colors colors;
//	private Map<State, Boolean> pink;
//	private ConcurrentHashMap<State> hashMap;
//
//	public NNDFS(Graph graph, Map<State,Color> map,
//			ConcurrentHashMap<State> hashMap) {
//		this.graph = graph;
//		this.colors = new Colors(map);
//		this.pink = new HashMap<State, Boolean>();
//		this.hashMap = hashMap;
//
//	}
//
//	public void init() {
//	}
//
//	public void setThreadId(int thread) {
//		threadId = thread;
//	}
//
//	private Queue<State> getSortedQueue(State s) {
//		Queue<State> result = new LinkedList<State>();
//
//		List<State> allStates = graph.post(s);
//		for (int i = 0; i < allStates.size(); i++) {
//			// TODO Slim maniertje om threads the verdelen.
//			result.add(allStates.get((threadId + i) % allStates.size()));
//		}
//
//		return result;
//	}
//
//	private boolean isRed(State s) {
//		return hashMap.getRed(s);
//	}
//
//	private void dfsRed(State s) throws Result {
//		pink.put(s, true);
//		Queue<State> sortedQueue = getSortedQueue(s);
//		int states = sortedQueue.size();
//		for (int i = 0; i < states; i++) {
//			State t = sortedQueue.remove();
//			if (colors.hasColor(t, Color.CYAN)) {
//				throw new CycleFound();
//			}
//			Boolean b = pink.get(t);
//			if ((b == null || b == false) && !isRed(t)) {
//				dfsRed(t);
//			}
//
//			// else if (colors.hasColor(t, Color.BLUE)) {
//			// colors.color(t, Color.RED);
//			// dfsRed(t);
//			// }
//		}
//
//		if (s.isAccepting()) {
//			decrementCounter(s);
//			awaitCounterIsZero(s);
//		}
//		
//		// Make s red
//		hashMap.makeRed(s);
//		
//		pink.put(s, false);
//
//	}
//
//	private void awaitCounterIsZero(State s) {
//		boolean running = true;
//		while (running) {
//			running = !checkZero(s);
//		}
//	}
//
//	private boolean checkZero(State s) {
//		return hashMap.getCounter(s) == 0;
//	}
//
//	private void decrementCounter(State s) {
//		hashMap.decrementCounter(s);
//	}
//
//	private void incrementCounter(State s) {
//		hashMap.incrementCounter(s);
//	}
//
//	private void dfsBlue(State s) throws Result {
//		colors.color(s, Color.CYAN);
//		Queue<State> sortedQueue = getSortedQueue(s);
//		int states = sortedQueue.size();
//		for (int i = 0; i < states; i++) {
//			State t = sortedQueue.remove();
//			if (colors.hasColor(t, Color.WHITE) && !isRed(t)) {
//				dfsBlue(t);
//			}
//		}
//		if (s.isAccepting()) {
//			incrementCounter(s);
//			dfsRed(s);
//		}
//		colors.color(s, Color.BLUE);
//
//	}
//
//	private void nndfs(State s) throws Result {
//		dfsBlue(s);
//		throw new NoCycleFound();
//	}
//
//	public void ndfs() throws Result {
//		nndfs(graph.getInitialState());
//	}
//}
